package game.client;

public class StringMatch2D {

  public static void main(String[] args) {
      char[][] text = {
                                 { 'a', 'b', 'a', 'b', 'a' },
                                 { 'a', 'b', 'a', 'b', 'a' },
                                 { 'a', 'b', 'b', 'a', 'a' },
                                 { 'a', 'b', 'a', 'a', 'b' },
                                 { 'b', 'b', 'a', 'b', 'a' }
                               };
      char[][] pattern = {
                             { 'a', 'b' },
                             { 'b', 'a' }
                               };

      matrixPatternMatch(text, pattern);
  }

  private static void matrixPatternMatch(char[][] text, char[][] pattern) {
      // pre-process
      int[] patternStamp = new int[pattern[0].length];
      int[] textStamp = new int[text[0].length];

      caculateStamp(pattern, pattern.length, patternStamp);
      caculateStamp(text, pattern.length, textStamp);

      int[] next = new int[patternStamp.length];
      caculateNext(patternStamp, next);

      for (int i = 0; i < (text.length - pattern.length + 1); i++) {
              int col = isMatch(patternStamp, textStamp, next);
              if (col != -1) {
                      System.out.println("found");
                      System.out.println(i+", "+col);
                  }

              // move down
              if(i < text.length - pattern.length)
                      caculateNextStamp(text, pattern.length, textStamp, i);
          }

  }

  private static int isMatch(int[] patternStamp, int[] textStamp, int[] next) {
      int i = 0, j = 0;
      while (j < patternStamp.length && i < textStamp.length) {
              if (j == -1 || patternStamp[j] == textStamp[i]) {
                      i++;
                      j++;
                  } else {
                      j = next[j];
                  }
          }

      if (j == patternStamp.length) {
              return i-j;
          } else {
              return -1;
          }
  }

  private static void caculateNext(int[] pattern, int[] next) {
      next[0] = -1;

      int i = 0, j = -1;
      while(i<pattern.length-1) {
              if(j==-1 || pattern[i] == pattern[j]) {
                      i++;
                      j++;
                      next[i] = j;
                  } else {
                      j = next[j];
                  }
          }

  }

  private static void caculateNextStamp(char[][] text, int height,
  int[] textStamp, int row) {
      int d = (int) Math.pow(26, height-1);
      for (int i = 0; i < textStamp.length; i++) {
              textStamp[i] = 26 * (textStamp[i] - d * text[row][i]) + text[row + height][i];
          }
  }

  private static void caculateStamp(char[][] input, int height, int[] result) {
      for (int i = 0; i < result.length; i++) {
              result[i] = 0;
              for (int j = 0; j < height; j++) {
                      result[i] = 26 * result[i] + input[j][i];
                  }
          }
  }

}
